package com.tree;

import javax.sound.midi.Soundbank;

/**
 * @BelongsProject: DataStructures
 * @BelongsPackage: com.tree
 * @Author: 江岸
 * @CreateTime: 2021-03-15 21:23
 * @Description: 线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        GoodNode root = new GoodNode(1, "root");
        GoodNode node3 = new GoodNode(3, "tom");
        root.leftNode = node3;
        GoodNode node6 = new GoodNode(6, "jack");
        root.rightNode = node6;
        GoodNode node8 = new GoodNode(8, "lina");
        node3.leftNode = node8;
        GoodNode node10 = new GoodNode(10, "marry");
        node3.rightNode = node10;
        GoodNode node14 = new GoodNode(14, "smith");
        node6.leftNode = node14;

        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.root = root;

//        //以10号节点测试
//        System.out.println("线索化之前");
//        System.out.println(node10.leftNode);
//        System.out.println(node10.rightNode);
//        tree.ThreadedFun(root);
//        System.out.println("线索化之后");
//        System.out.println(node10.leftNode);
//        System.out.println(node10.rightNode);

        //线索化前后使用不同方式遍历
        System.out.println("线索化之前");
        tree.infixOrder();
        tree.ThreadedFun(root);
        System.out.println("线索化之后");
        tree.threadedOrder();

    }
}
class ThreadedBinaryTree{
    public GoodNode root;

    //前驱节点
    public GoodNode pre = null;


    //中序线索化方法
    public void ThreadedFun(GoodNode goodNode){
        //如果node为null，就不可以继续线索化
        if (goodNode==null){
            return;
        }
        //(一)左节点
        ThreadedFun(goodNode.leftNode);

        //(二)当前节点
        if (goodNode.leftNode ==null){
            //让当前节点的左指针指向前驱节点
            goodNode.leftNode = pre;
            goodNode.leftType = 1;
        }
        if (pre !=null && pre.rightNode==null){
            //让当前节点的前一个节点来处理后继节点
            pre.rightNode = goodNode;
            pre.rightType = 1;
        }
        //每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = goodNode;

        //(三)右节点
        ThreadedFun(goodNode.rightNode);
    }

    //正常中序遍历
    public void infixOrder(){
        root.infixOrder();
    }

    //遍历线索二叉树
    //线索化之后，不能再用前中后序遍历了，因为左右指向都不为空，会造成死循环
    public void threadedOrder(){
        GoodNode node = root;
        while(node!=null){
            //找到第一个有前驱节点的节点  Null←node
            while(node.leftType==0){
                node = node.leftNode;
            }
            //输出该节点
            System.out.println(node);
            //如果后面有后驱节点，可以一直输出
            while (node.rightType==1){
                node = node.rightNode;
                System.out.println(node);
            }
            //当右节点不为后驱节点时候，把node移动到右节点上
            node = node.rightNode;
        }
    }

}
class GoodNode{
    public int id;
    public String name;
    public GoodNode leftNode;
    public GoodNode rightNode;
    //type=0代表指向子树，type=1代表指向前驱后继节点
    public int leftType = 0;
    public int rightType = 0;

    public GoodNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public GoodNode() {
    }

    @Override
    public String toString() {
        return "GoodNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.leftNode!=null) this.leftNode.preOrder();
        if (this.rightNode!=null) this.rightNode.preOrder();
    }
    //中序遍历
    public void infixOrder(){
        if (this.leftNode!=null) this.leftNode.infixOrder();
        System.out.println(this);
        if (this.rightNode!=null) this.rightNode.infixOrder();
    }
    //后序遍历
    public void postOrder(){
        if (this.leftNode!=null) this.leftNode.postOrder();
        if (this.rightNode!=null) this.rightNode.postOrder();
        System.out.println(this);
    }


}